// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package sort

// A type, typically a collection, that satisfies sort.Compare can be
// binary searched by the routines in this package.  The methods require that the
// elements of the collection be enumerated by an integer index.
type Compare interface {
	Interface
	// Cmp compares key with element at index i, returning -1, 0, or 1
	Cmp(key interface{}, i int) int
}

// Binary search. Requires data to be sorted. General but slow.
// for int, float or string use: BsearchInts, BsearchFloats or BsearchStrings
func Bsearch(key interface{}, data Compare) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		cmp := data.Cmp(key, mid)
		switch {
		case cmp < 0:
			hi = mid - 1
		case cmp > 0:
			lo = mid + 1
		case cmp == 0:
			return mid
		}
	}
	return -1
}

// Cmp is used only for Bsearch, not needed by Sort
func (p IntArray) Cmp(key interface{}, i int) int {
	k := key.(int)
	if k > p[i] {
		return 1
	} else if k < p[i] {
		return -1
	}
	return 0
}

// Cmp is used only for Bsearch, not needed by Sort
func (p FloatArray) Cmp(key interface{}, i int) int {
	k := key.(float)
	if k > p[i] {
		return 1
	} else if k < p[i] {
		return -1
	}
	return 0
}

// Cmp is used only for Bsearch, not needed by Sort
func (p StringArray) Cmp(key interface{}, i int) int {
	k := key.(string)
	if k > p[i] {
		return 1
	} else if k < p[i] {
		return -1
	}
	return 0
}

// Bsearch is a convenience method
func (p IntArray) Bsearch(key int) int { return Bsearch(key, p) }

// Bsearch is a convenience method
func (p FloatArray) Bsearch(key float) int { return Bsearch(key, p) }

// Bsearch is a convenience method
func (p StringArray) Bsearch(key string) int { return Bsearch(key, p) }

//BsearchInts does a fast binary search of an array of ints
//Requires data to be sorted.
func BsearchInts(key int, data IntArray) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if key < data[mid] {
			hi = mid - 1
		} else if key > data[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

//BsearchFloats does a fast binary search of an array of floats
//Requires data to be sorted.
func BsearchFloats(key float, data FloatArray) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if key < data[mid] {
			hi = mid - 1
		} else if key > data[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

//BsearchStrings does a fast binary search of an array of strings
//Requires data to be sorted.
func BsearchStrings(key string, data StringArray) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if key < data[mid] {
			hi = mid - 1
		} else if key > data[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

// BsearchInts is a convenience method
func (p IntArray) BsearchInts(key int) int { return BsearchInts(key, p) }

// BsearchFloats is a convenience method
func (p FloatArray) BsearchFloats(key float) int {
	return BsearchFloats(key, p)
}

// BsearchStrings is a convenience method
func (p StringArray) BsearchStrings(key string) int {
	return BsearchStrings(key, p)
}
